/**
 * 从一个中缀表达式的二叉树还原字符串
 */

#include<iostream>
#include<string>
using namespace std;

typedef struct node
{
    string data;
    struct node *left,*right;
    node(){
        node("");
    }
    node(string x){
        this->data=x;
        this->left=nullptr;
        this->right=nullptr;
    }
}BTree;

//将子树转换为转换为表达式
void toStatement(BTree* root){
    if(root==nullptr)return;
    //只有当符号节点的时候才需要加上括号
    //而符号节点就是哪些有子树（不管是一个还是两个）的节点
    if(root->left!=nullptr||root->right!=nullptr) cout<<"(";
    toStatement(root->left);
    cout<<root->data;
    toStatement(root->right);
    if(root->left!=nullptr||root->right!=nullptr) cout<<")";
}
//最外层没有括号，为了方便算法实现,多加一层函数，单独处理根节点
void func(BTree* root){
    toStatement(root->left);
    cout<<root->data;
    toStatement(root->right);
}

int main(void){
    BTree* root=new BTree();
    root->data="*";
    root->left=new BTree("+");
    root->left->left=new BTree("a");
    root->left->right=new BTree("b");
    root->right=new BTree("*");
    root->right->left=new BTree("c");
    root->right->right=new BTree("-");
    root->right->right->right=new BTree("d");
    func(root);
}
//(a+b)*(c*(-d))